%Preâmbulo
\documentclass[12pt,a4paper]{article}
\usepackage{amssymb,amsmath,amsthm, mathtools}
\usepackage[usenames,dvipsnames]{color}
%\usepackage{ntheorem}
\newtheorem{hyp}{Hip\'{o}tese} 
\newcounter{subhyp} 
\newcommand{\subhyp}{ 
  \setcounter{subhyp}{0} 
  \renewcommand\thehyp{\protect\stepcounter{subhyp}% 
  \arabic{hyp}\alph{subhyp}\protect\addtocounter{hyp}{-1}} 
} 
\newcommand{\normhyp}{ 
  \renewcommand\thehyp{\arabic{hyp}} 
  \stepcounter{hyp} 
} 
\newtheorem{theorem}{Teorema}[section]
\newtheorem*{theoremnon}{Teorema}
\newtheorem{lemma}[theorem]{Lema}
\newtheorem{proposition}[theorem]{Proposi\c{c}\~{a}o}
\newtheorem{corollary}[theorem]{Corol\'{a}rio}

%\newenvironment{proof}[1][Prova]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{definition}[1][Defini\c{c}\~{a}o]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{example}[1][Examplo]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{remark}[1][Remark]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

%\newcommand{\qed}{\nobreak \ifvmode \relax \else
%      \ifdim\lastskip<1.5em \hskip-\lastskip
%      \hskip1.5em plus0em minus0.5em \fi \nobreak
%      \vrule height0.75em width0.5em depth0.25em\fi}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\usepackage{alltt}
\usepackage{tkz-berge}
\usepackage{wrapfig}
%\usepackage{minted}
\usepackage{listings}
\usepackage{subfloat}
\usepackage{url}
\usepackage{cite}
\usepackage{multirow}
\usepackage{unicamplogo}
\usepackage[portuguese]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[lofdepth]{subfig}
\usepackage[utf8]{inputenc}
\usepackage{textcomp}
%\usepackage{listingsutf8}%linguagem de programação
\usepackage{xcolor}
\usepackage{color}
\usepackage{graphicx}
\usepackage[export]{adjustbox}
\usepackage{wrapfig}
\graphicspath{ {imagens/} }
\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92} 
\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\definecolor{bg}{rgb}{0.85,0.85,0.85}%cor de background: caixa de fundo do código
%Definições para o pacote listings: linguagem de programação
\lstset{
  backgroundcolor=\color{backcolour},   % choose the background color; you must add\usepackage{color}
  basicstyle=\tiny,        % the size of the fonts that are used for the code
  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  breaklines=true,                 % sets automatic line breaking
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{mygreen},    % comment style
  escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
  extendedchars=true,              % lets you use non-ASCII characters;
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 % keeps spaces in text, useful for keeping indentation
  keywordstyle=\color{black},       % keyword style
  language=C,                	  % the language of the code
  numbers=left,                    % where to put the line-numbers; possible values are 
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{blue}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-break
  showspaces=false,                % show spaces everywhere adding particular underscores;
  showstringspaces=false,          % underline spaces within strings only
  showtabs=false,                  % show tabs within strings adding particular underscores
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
  stringstyle=\color{black},     % string literal style
  tabsize=2,                       % sets default tabsize to 2 spaces
  title=\lstname,                   % show the filename of files included with \lstinputlisting; also try caption instead of title
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    extendedchars=false,
    	inputencoding=utf8,
    	literate=%
        {é}{{\'{e}}}1
        {è}{{\`{e}}}1
        {ê}{{\^{e}}}1
        {ë}{{\¨{e}}}1
        {É}{{\'{E}}}1
        {Ê}{{\^{E}}}1
        {û}{{\^{u}}}1
        {ú}{{\'{u}}}1
        {â}{{\^{a}}}1
        {à}{{\`{a}}}1
        {á}{{\'{a}}}1
        {ã}{{\~{a}}}1
        {Á}{{\'{A}}}1
        {Â}{{\^{A}}}1
        {Ã}{{\~{A}}}1
        {ç}{{\c{c}}}1
        {Ç}{{\c{C}}}1
        {õ}{{\~{o}}}1
        {ó}{{\'{o}}}1
        {ô}{{\^{o}}}1
        {Õ}{{\~{O}}}1
        {Ó}{{\'{O}}}1
        {Ô}{{\^{O}}}1
        {î}{{\^{i}}}1
        {Î}{{\^{I}}}1
        {í}{{\'{i}}}1
        {Í}{{\~{Í}}}1
}
\usepackage[right=2.5cm,left=2.5cm,top=2.5cm,bottom=2.5cm]{geometry}
\usepackage{indentfirst}
\usepackage{float}
%PACOTE DO IC
\usepackage{logo-ic-unicamp}
%PACOTE DO IMECC
\usepackage{logo-unicamp}
%REDEFINE O COMANDO RESUMO
\renewcommand\thesubsubsection{\Roman{subsubsection}} 
\newcommand{\resumo}[2]{\noindent{\textsl{\space#1: }#2}\\}
\usepackage[hidelinks]{hyperref}
\usepackage{enumerate}
\usepackage{marginnote}
%Preparando para o PSEUDOCODIGO
\usepackage{algpseudocode}
\usepackage{algorithm}
\makeatletter
\renewcommand{\ALG@name}{Algoritmo}
\makeatother
\makeatletter
\renewcommand{\listalgorithmname}{Lista de Algoritmos}
\makeatother    
% Declaracoes em Português
\floatname{algorithm}{Algoritmo}
\usepackage{caption}
\DeclareCaptionLabelFormat{something}{#2.#1.}
\renewcommand{\algorithmicrequire}{\textbf{\color{blue}{Entrada: }}}
\renewcommand{\algorithmicensure}{\textbf{\color{violet}{Saída: }}}
\algrenewcommand\algorithmicend{\textbf{fim}}
\algrenewcommand\algorithmicdo{\textbf{faça}}
\algrenewcommand\algorithmicwhile{\textbf{enquanto}}
\algrenewcommand\algorithmicfor{\textbf{para}}
\algrenewcommand\algorithmicif{\textbf{se}}
\algrenewcommand\algorithmicthen{\textbf{então}}
\algrenewcommand\algorithmicelse{\textbf{senão}}
\algrenewcommand\algorithmicreturn{\textbf{devolve}}
\algrenewcommand\algorithmicfunction{\textbf{função}}
\algrenewcommand\algorithmicprocedure{\textbf{procedimento}}
% Rearranja os finais de cada estrutura
\algrenewtext{EndWhile}{\algorithmicend\ \algorithmicwhile}
\algrenewtext{EndFor}{\algorithmicend\ \algorithmicfor}
\algrenewtext{EndIf}{\algorithmicend\ \algorithmicif}
\algrenewtext{EndFunction}{\algorithmicend\ \algorithmicfunction}
% O comando For, a seguir, retorna 'para #1 -- #2 até #3 faça'
\algnewcommand\algorithmicto{\textbf{até}}
\algrenewtext{For}[3]%
{\algorithmicfor\ #1 $\gets$ #2 \algorithmicto\ #3 \algorithmicdo}
%Pacote para colocaração de código no uso do MINTED
\usepackage{footnote}
\usepackage{etoolbox}
\usepackage{tcolorbox}
\tcbuselibrary{minted,skins}
\newtcblisting{myc}{
  listing engine=minted,
  colback=bg,
  colframe=black!70,
  listing only,
  minted style=colorful,
  minted language=c,
  minted options={linenos=true,texcl=true},
  left=1mm,
}
\renewcommand\listingscaption{Implementação}
\renewcommand\listoflistingscaption{Lista de Implementações}
\author{Raphael Marques Franco}
\begin{document}
%capa
\begin{titlepage}
\begin{center}
\hspace{0.1cm}\LogoUnicamp\\\vspace{0.2cm}
\Large{\textbf{\textit{Universidade Estadual de Campinas}}} \\\vspace{0.4cm}

\hspace{0.1cm}\LogoIcUnicamp\\\vspace{0.2cm}
\Large{\textbf{\textit{Instituto de Computação}}} \\\vspace{1cm}
\Large{
\textbf{MC458\\\vspace{0.2cm}
\textit{Projeto e Análise de Algoritmos I}\\\vspace{0.4cm}
Relatório\\ Laboratório 2}}\\\vspace{0.4cm}
\large{\textit{"Análise, implementação e teste de desempenho de uma solução para o problema do Conjunto Independente Máximo (CIM)"}}\\\vspace{2cm}
\Large{
\textnormal{Alunos: Lucas Henrique Morais RA136640\\
email: \textit{\color{blue}{lhmaster2@gmail.com }}\\\vspace{0.2cm}
 Raphael Marques Franco RA035501\\\vspace{0.2cm}
email: \textit{\color{blue}{poli.unicamp@gmail.com}}\\\vspace{4cm}
Campinas\\\today{}}}
\end{center}
\end{titlepage}
%fim da capa


%Sumario
%fim do Sumario
\resumo{Resumo}{Este relatório descreve o projeto de algoritmos por indução para resolução do Problema do Conjunto Independente Máximo. Realizando a corretude do algoritmo, análise assintótica e implementação em linguagem C. Por fim discutimos de maneira experimental a implementação realizada.}%colocar informação dos resultados}
\section{Introdução}
%Uma seção introdutória, descrevendo o problema proposto.
%Cinco passo para um pensamento algoritmico bem sucedido estão em vermelho!
Atualmente um dos temas de enorme destaque em publicações e consideráveis investimentos em pesquisas em todo o mundo é o de redes complexas. As redes complexas são hoje a teoria e a ferramenta que possibilita a pesquisa interdisciplinar num nível nunca antes dominado e conhecido pela humanidade. Sendo que a estrutura que encerra aquilo que denominamos redes complexas nada mais do que um grafo. Considerando isso temos como consequência que os avanços em teoria dos grafos, vistos desde seus primórdios com o marco histórico da publicação da resolução do \textit{problema das sete pontes de Königsberg}, em 1736 por Euler, tanto em representações, métodos e algoritmos tendem à alavancar as pesquisas em redes complexas. Destacando que os métodos e algoritmos em grafos existentes permitem facilitar tanto o armazenamento quanto o processamento de informações numa escala conhecida como \textit{Big Data}, um dos problemas existentes na manipulação de redes complexas. Visto a importância do desenvolvimento da teoria dos grafos vemos como elemento da teoria dos grafos um problema que este trabalho contempla, \textit{o problema do Conjunto Independente Máximo}, o qual será tratado sob a ótica da análise e projeto de algoritmos. Este problema é um problema da classe NP-difícil, sendo a força bruta para obtenção de uma solução exata da ordem de $\mathcal{O}(n^{2}2^{n})$\protect\footnotemark . A solução exata sendo de ordem assintótica muito alta leva a existência de inúmeras técnicas e abordagens heurísticas como veremos aqui apresentando a nossa no desenvolvimento do algoritmo.
\footnotetext{\url{http://en.wikipedia.org/wiki/Independent_set_\%28graph_theory\%29}}
\section{Modelagem}
%Uma seção descrevendo a modelagem criada, se houver, e também explicando textualmente ideia usada e o funcionamento dos algoritmos projetados para resolver o problema. Os algoritmos também deverão ser detalhados em pseudo-código. Aqui também deverão ser descritas as entradas válidas e as saídas esperadas para os experimentos.
\subsection{{\color{red}Formulando o problema}}\label{Formulaop}
Para melhor atendermos os requisitos do laboratório formulamos as definições e notações que serão utilizadas para melhor explorar o projeto e análise de algoritmo do problema do Conjunto Independente Máximo ao longo deste trabalho:
\begin{definition}{1}
\\\textbf{Grafo} $\mathbf{\mathcal{G}}$ é o conjunto formado pelo par ordenado $\mathcal{G=(V, E)}$, onde $\mathcal{V}$ é o conjunto do vértices ou nós e $\mathcal{E}$ é o conjunto das arestas, tal que para cada par existente de vértices pertencentes a $\mathcal{V}$, relação denominada conexão, temos um único um elemento, conhecido como aresta, pertencente a $\mathcal{E}$. 
\end{definition}
\begin{definition}{2}
\\\textbf{Grafo Não Direcionado} $\mathbf{\mathcal{G}}$ é o grafo $\mathcal{G=(V, E)}$ tal que a relação conexão se dá atráves do par não ordenado de vértices ou nós de $\mathcal{V}$.
\begin{center}
 $\forall v_i,v_j \in \mathcal{V} \; : e_i=\{ v_i,v_j \} , \; e_j= \{ v_j,v_i \} \land i \neq j \Leftrightarrow e_i = e_j$
\end{center}
\end{definition}
\begin{definition}{3}
\\\textbf{Grafo  Direcionado ou Digrafo} $\mathsf{G}$ é o grafo $\mathsf{G=(\mathcal{V}, \mathcal{E})}$ tal que a relação conexão que representa um elemento de $\mathcal{E}$ se dá atráves do par ordenado de vértices ou nós de $\mathcal{V}$:\\\vspace{-.5cm}
\begin{center}
 $\forall v_i,v_j \in \mathcal{V} \; : e_i=(v_i,v_j), \; e_j=(v_j,v_i) \Rightarrow e_i \neq e_j \Leftrightarrow i \neq j$
\end{center}
\begin{definition}{4}
\\\textbf{Adjacência} é uma propriedade relacionada aos vértices de um grafo $\mathcal{G=(V, E)}$ tal que se existe uma aresta $\mathit{e} \in \mathcal{E}$ na qual os vértices $\mathit{v}_i,\; \mathit{v_j}\in \mathcal{V}$ estão conectados, dizemos então que $\mathit{v_i}$ e $\mathit{v_j}$ são adjacentes. 
\end{definition}
\begin{definition}{5}
\\\textbf{Conjunto Independente($\mathbf{\mathcal{V^I}}$)}, dado um grafo $\mathcal{G=(V, E)}$, é qualquer conjunto possível de se formar com os vértices pertencentes à $\mathcal{V}$ sendo que não existem nenhum dos vértices tomados dois a dois adjacentes. \\\vspace{-0.5cm}
\begin{center}
$\mathcal{S}:\forall\; (\mathcal{V^I}  \subset \mathcal{V})\; \forall (\mathit{u,v\:} \in \mathcal{V^I})\::\:\mathit{u\neq v}\:\Rightarrow\:\mathit{\{ u,v\} }\notin \mathcal{E}$
\end{center}
\end{definition}
\end{definition}
\begin{definition}{6}
\\\textbf{Conjunto Independente Máximo($\mathbf{\mathcal{V_{M}^{I}}}$)}: dado um grafo $\mathcal{G=(V, E)}$ e o conjunto $\mathcal{V^I}$ formado por todos os conjuntos independentes possíveis. Temos que os elemento dentro do conjunto $\mathcal{V^I}$ com maior cardinalidade possível que conseguimos obter serão elementos pertencentes ao Conjunto Independente Máximo($\mathbf{\mathcal{V_{M}^{I}}}$).\\\vspace{-.5cm} 
\begin{eqnarray}
\text{ Os elementos formado}&\text{por}& \text{conjuntos independentes do grafo } \mathcal{G=(V, E)}:\nonumber \\
\mathcal{V}_{1}^\mathcal{I},\mathcal{V}_2^\mathcal{I}, \dots, \mathcal{V}_{\left\vert{\mathcal{S}}\right\vert}^\mathcal{I} &\in& \mathcal{S}\nonumber\\
\exists\; (\mathcal{V_{M}^{I}}  \in  \mathcal{S})\;&:&\left\vert{\mathcal{V_{M}^{I}}}\right\vert=max(\left\vert{\mathcal{V}_{1}^\mathcal{I}}\right\vert, \left\vert{\mathcal{V}_2^\mathcal{I}}\right\vert, \dots, \left\vert{\mathcal{V}_{\left\vert{\mathcal{S}}\right\vert}^\mathcal{I}}\right\vert) \nonumber\\
 \nonumber 
\end{eqnarray}
\end{definition}
\subsection{Motivação dos Algoritmos}
\textbf{A1} :
o algoritmo testa por força bruta todas as possibilidades de inclusão ou não de cada nó do grafo G em busca da configuração de maior cardinalidade que respeite as condições de um
conjunto independente, isto é, que não haja nenhuma aresta entre seus nós.
Para cada nó v de G, o algoritmo compara os cenários:
(1): Em que v está presente no CI
(2): Em que v não está presente no CI
Cada um dos casos leva a uma chamada recursiva do algoritmo para o subgrafo definido por:
(1): G / ({v} U Adj(v))
(2): G / {v}
A2
Este algoritmo, baseado no anterior, difere dele apenas pelo uso de duas heurísticas, a
saber:
(1): Todos os nós de grau nulo devem ser inclusos no CI.
(2): Todos os nós de grau igual a 1 devem ser inclusos no CI.
Estas duas heurísticas levam à remoção em tempo linear dos nós de baixo grau durante uma
única passagem de pré-processamento. Além disso, garantem que o algoritmo respeite agora
a seguinte relação de recorrência:
\begin{eqnarray}
	T_2(n) &\leq& max (T_2(n-1);\; T_2(n-2);\; T_2(n-1) + T_2(n-4)) + p(n)\nonumber\\
 	\Rightarrow T_2 &=&\Theta(1.380^n)
\end{eqnarray}
A3\\
O algoritmo (3) baseia-se no algoritmo (2), diferindo dele apenas pela inclusão de uma
nova heurística, a saber:
(1) Após o pré-processamento dos nós de baixo grau, os nós devem ser sempre removidos
a partir do nó de maior grau para o de menor grau (ordem decrescende de graus).
Assim fazendo, procura-se garantir que, em toda nova invocação recursiva do algoritmo, se
remova o maior número possível de vértices, levando a sub-problemas de tamanho tipicamente
menor dos que os verificados para o algoritmo (2).
Espera-se conseguir, assim, um menor tempo de execução para entradas típicas.	
\subsection{{\color{red}Desenvolvendo o Algoritmo}}

\section{Estrutura do programa}
%Uma seção descrevendo a estrutura do programa fonte projetado pelo grupo. Dê detalhes suficientes para que a estrutura do fluxo de controle e \subsection{{\color{red}Entendendo o problema}}\vspace{0.5cm}
\subsection{{\color{red}Implementando o Algoritmo}}

\begin{minted}
	[
	frame=single,
	framesep=2mm,
	baselinestretch=1.2,
	bgcolor=bg,
	fontsize=\footnotesize,
	linenos
	]
	{c}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 100
typedef int MatrizAdjacencia[N][N];
/*
* Estrutura de dados que marca os nos presentes.
* Para todos i entre 0 e 99, inclusive, o vetor vale
* 1, caso o no i enteja presente, ou 0, caso contrario.
*/
typedef struct{
	int *l;
	int size;
	int maxSize;
	int firstNode;
} ListOfNodes;
/*
*
*/
typedef struct{
	MatrizAdjacencia matrix;
	int n;
	int m;
} Graph;
/*
*
*/
void clearMatrix (MatrizAdjacencia matrix){
	int i, j;
	for (i = 0; i < N; i++)
	for (j = 0; j < N; j++)
	matrix[i][j] = 0;
}

\end{minted} 
\newpage 
\begin{minted}
		[
		frame=single,
		framesep=2mm,
		baselinestretch=1.2,
		bgcolor=bg,
		firstnumber=39,
		fontsize=\footnotesize,
		linenos
		]
		{c}
/*
*
*/
ListOfNodes setupList (int maxSize){
	ListOfNodes new;
	new.l = calloc(maxSize, sizeof(int));
	new.size = 0;
	new.maxSize = maxSize;
	new.firstNode = maxSize + 1;	
	return new;
}
/*
*
*/
void freeList (ListOfNodes *list){
	free(list->l);
}
/*
 *
 */
int isThereNode (ListOfNodes *list, int pos){
	return list->l[pos];
}
/*
*
*/
ListOfNodes copyList (ListOfNodes *original){
	ListOfNodes new;
	int i;
	new = setupList(original->maxSize);
	new.firstNode = original->firstNode;
	new.maxSize = original->maxSize;
	new.size = original->size;
	for (i = 0; i < original->maxSize; i++)
	new.l[i] = original->l[i];
	return new;	
}
/*
 *
 */
int nodeDegree (ListOfNodes *list, int pos, MatrizAdjacencia matrix){
	int i, deg;	
	for (i = 0, deg = 0; i < list->maxSize; i++)
	deg += matrix[pos][i];
	return deg;
}

\end{minted}
\newpage
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
firstnumber=85,
fontsize=\footnotesize,
linenos
]
{c}
/*
*
*/
void setFirstNode (ListOfNodes *list, int offset){
	int i;
	for (i = offset + 1; i < list->maxSize; i++)
	{
		if (list->l[i])
		{
			list->firstNode = i;
			return;
		}
	}
}
/*
 *
 */
void removeNode (int nodePos, ListOfNodes *list)
{
	if (list->l[nodePos]){
		list->size--;	
		list->l[nodePos] = 0;	
		if (list->firstNode == nodePos)
		setFirstNode(list, nodePos);
	}
}	
/*
 *
 */
void removeNodeAndAdjacency (int nodePos, ListOfNodes *list, MatrizAdjacencia matrix)
{
	int i;
	for (i = 0; i < list->maxSize; i++){
		if (matrix[nodePos][i] == 1)
		removeNode(i, list);
	}
	removeNode(nodePos, list);
}
\end{minted}
\newpage
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
firstnumber=123,
fontsize=\footnotesize,
linenos
]
{c}	
/*
*
*/
void addNode (int nodePos, ListOfNodes *list){
	if (!list->l[nodePos]){
		list->size++;
		list->l[nodePos] = 1;
		if (nodePos < list->firstNode)
		list->firstNode = nodePos;
	}
}
/*
*
*/
void addNodeAndAdjacency (int nodePos, ListOfNodes *list, MatrizAdjacencia matrix){
	int i;
	for (i = 0; i < list->maxSize; i++){
		if (matrix[nodePos][i] == 1)
		addNode(i, list);
	}
	addNode(nodePos, list);
}
/*
*
*/
int getFirstNode(ListOfNodes *list)
{
	int i;
	for (i = 0; i < list->maxSize; i++){
		if (list->l[i] == 1)
		return i;
	}
	return -1;
}
/*
* Funcao que adiciona a aresta a-b a Matriz de Adjacencia *matrix
*/
void addEdge (int a, int b, MatrizAdjacencia matrix){
	matrix[a][b] = 1;
	ma//printf("Adicionou-se aresta %d-%d\n", a, b);
	trix[b][a] = 1;
}

/**
* Funcao que remove a aresta a-b da Matrix de Adjacencia matrix
*/
void removeEdge (int a, int b, MatrizAdjacencia matrix){
	matrix[a][b] = 0;
	matrix[b][a] = 0;
}
\end{minted}
\newpage
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
firstnumber=173,
fontsize=\footnotesize,
linenos
]
{c}		
/*
*
*/
int max (int a, int b){
	return a > b ? a : b;
}
/*
*
*/
unsigned int coreA1(ListOfNodes *list, MatrizAdjacencia M){
	ListOfNodes copy;
	int m;
	// Casos base
	if (list->size == 1) return 1;
	else if (list->size == 0) return 0;
	copy = copyList(list);
	removeNode(list->firstNode, &copy);//No nao presente
	removeNodeAndAdjacency(list->firstNode, list, M);//No presente
	m = max(coreA1(&copy, M), 1 + coreA1(list, M));
	freeList(&copy);
	return m;
}
/*
*
*/
unsigned int scoreA1(ListOfNodes *list, MatrizAdjacencia M){
	ListOfNodes copy;
	int m, m1, m2;
	int first;
	// Casos base
	if (list->size == 1) return 1;
	else if (list->size == 0) return 0;
	first = list->firstNode;
	removeNode(first, list);
	m1 = scoreA1(list, M);
	addNode(first, list);
	removeNodeAndAdjacency(first, list, M);
	m2 = 1 + scoreA1(list, M);
	addNodeAndAdjacency(first, list, M);
	return max(m1, m2);
}
\end{minted}
\newpage
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
firstnumber=214,
fontsize=\footnotesize,
linenos
]
{c}		
/*
*
*/
unsigned int coreA2(ListOfNodes *list, MatrizAdjacencia M){
	ListOfNodes copy;
	int m, aux;
	int i;
	// Casos base
	if (list->size == 1) return 1;
	else if (list->size == 0) return 0;
	for (i = 0; i < list->maxSize; i++){
		if (isThereNode(list, i)){
			aux = nodeDegree(list, i, M);
			if (aux < 2){
				if (aux == 0){
					removeNode(i, list);
					return 1 + coreA2(list, M);
				}
				else{
					removeNodeAndAdjacency(i, list, M);
					return 1 + coreA2(list, M);
				}
			}
		}
	}
	copy = copyList(list);
	removeNode(list->firstNode, &copy);//No nao presente
	removeNodeAndAdjacency(list->firstNode, list, M);//No presente
	m = max(coreA2(&copy, M), 1 + coreA2(list, M));	
	freeList(&copy);
	return m;
}
/*
*
*/
unsigned int A1(unsigned int n, MatrizAdjacencia M){
	ListOfNodes list;
	int i;
	unsigned int m;
	list = setupList(N);
	list.size = n;
	list.firstNode = 0;
	for (i = 0; i < n; i++) list.l[i] = 1;
	m = scoreA1(&list, M);
	freeList(&list);
	return m;
}
\end{minted}
\newpage
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
firstnumber=261,
fontsize=\footnotesize,
linenos
]
{c}			
/*
*
*/
unsigned int A2(unsigned int n, MatrizAdjacencia M){
	ListOfNodes list;
	int i;
	unsigned int m;
	list = setupList(N);
	list.size = n;
	list.firstNode = 0;
	for (i = 0; i < n; i++)	list.l[i] = 1;
	m = coreA2(&list, M);
	freeList(&list);
	return m;
}
/*
*
*/
double A1Handler (int n, MatrizAdjacencia M){
	//TODO mudar (atualmente esta retornando a cardinalidade maxima do conjunto independente)
	return A1(n, M);
}
/*
*
*/
double A2Handler (int n, MatrizAdjacencia M){
	return A2(n, M);
}
/*
*
*/
double A3Handler (int n, MatrizAdjacencia M){
	return 0;
}

/**
* Funcao de geracao de grafos aleatorios.
* O grafo retornado possui n nos e m arestas.
*/
Graph graphMaker (int n, int m){
	static int initialized = 0;
	Graph g;
	int i, j;
	g.n = n;
	g.m = 0;
	clearMatrix(g.matrix);
	if (!initialized){
		srand48(clock());
		initialized = 1;
\end{minted}
\newpage
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
firstnumber=310,
fontsize=\footnotesize,
linenos
]
{c}	
	{		
	while (g.m < m){
		i = (int) (n + 1) * drand48();
		j = (int) (n + 1) * drand48();
		if (!g.matrix[i][j] && (i != j)){
			g.m++;
			addEdge(i, j, g.matrix);
		}
	}
	return g;
}
/*
*
*/
void algTester (int iter, int n, int m){
	int i;
	Graph g;
	for (i = 0; i < iter; i++){
		g = graphMaker(n, m);
		printf("--Iteration %d--", i);
		printf("A1-ET: %fs\n", A1Handler(g.n, g.matrix));
		//printf("A2-ET: %fs\n", A2Handler(g.n, g.matrix));
		printf("\n");
	}
}
/*
*
*/
void algTesterWrap (void){
	int iter, n, m;
	printf("# of iterations: ");
	scanf("%d", &iter);
	printf("# of nodes: ");
	scanf("%d", &n);
	printf("# of edges: ");
	scanf("%d", &m);
	algTester(iter, n, m);
}
/*
*
*/
void IOHandler (void)
{
	int ng, n, m;
	int i, j;
	int v1, v2;
	MatrizAdjacencia M;
	scanf("%d %d %d", &ng, &n, &m);
\end{minted}
\newpage
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
firstnumber=358,
fontsize=\footnotesize,
linenos
]
{c}			
	for (i = 0; i < ng; i++){
		for (j = 0; j < m; j++){
			scanf("%d %d", &v1, &v2);
			M[v1][v2] = 1;
			M[v2][v1] = 1;
		}
		printf("Graph #%d\n", i);
		printf("A1-ET: %fs\n", A1Handler(n, M));
		printf("A2-ET: %fs\n", A2Handler(n, M));
		printf("A3-ET: %fs\n", A3Handler(n, M));
	}
}

int main (void){
	//IOHandler();
	algTesterWrap();
	return 0;
}
\end{minted}
		
\section{Resultados}
%Uma seção descrevendo os resultados computacionais obtidos, incluindo tabelas, gráficos e outras ferramentas que você considere úteis para a clareza do texto. Não esqueça de detalhar em que plataforma (hardware e software) os experimentos foram executados (CPU, memória, versão de compilador, flags especiais usados na compilação, etc.).
\subsection{{\color{red}Execução com dados e observação dos resultados}}
\section{Conclusão}
%Uma seção de conclusão, descrevendo o que você aprendeu com os experimentos

\color{black}
\section{Referências}
%\section{OUTROS}
% Outras seções, a critério do grupo.

\end{document}
